為何要討論外擴樹

AVL Tree 的調整比較困難，可以將操作的最差時間控制在 O(logn)
但 Splay Tree 透過比較簡單的調整，雖然最差時間會落在 O(n)，但 Amortized 後會變成 O(logn) 時間

何謂 Splay Tree

是一顆 Binary Search Tree，差別於每次 insert / delete / search 後，須針對 splay 起點做 splay operation

splay 起點

insert X: X 為 splay 起點
delete X: X 的 parent 為 splay 起點
search: X 為 splay 起點

Splay operation

將 splay Tree 變為 root，有利於未來方便操作。
有的時候我們 insert data 後就要馬上操作，將他移到 root 只須 O(1) 時間即可找到資料

Insert X into a splay tree

splay 操作則是一連串的 rotation，目的就是把 Splay 起點變為 Root

Delete X from a splay tree

splay 操作則是一連串的 rotation，目的就是把 Splay 起點變為 Root

總結

雖然 Splay operation 有可能導致斜曲樹，但因為 splay 點移到了 Root，操作就變成了 O(1)。所以總體來說的時間也會變回 O(logn)